#include "string_array.h"
#include <algorithm>
using namespace std;

myStr::myStr(const char* str) {
    length = 0;
    while (str[length] != '\0') {
        length++;
    }

    data = new char[length + 1];
    for (int i = 0; i <= length; i++) {
        data[i] = str[i];
    }

    next = new int[length];
    nextVal = new int[length];

    for (int i = 0; i < length; i++) {
        next[i] = -1;
        nextVal[i] = -1;
    }
}

myStr::~myStr() {
    delete[] data;
    delete[] next;
    delete[] nextVal;
}

void myStr::kmp_next() {
    int j = 0;
    int k = -1;
    int* tempNext = new int[length];
    tempNext[0] = -1;

    while (j < length - 1) {
        if (k == -1 || data[j] == data[k])
        {
            j++;
            k++;
            tempNext[j] = k;
        }
        else
            k = tempNext[k];
    }

    for (int i = 0; i < length; i++) {
        next[i] = tempNext[i] + 1;
    }

    delete[] tempNext;
}

void myStr::kmp_nextVal() {
    int* tempNext = new int[length];
    int j = 0, k = -1;
    tempNext[0] = -1;

    while (j < length - 1) {
        if (k == -1 || data[j] == data[k]) {
            j++; k++;
            tempNext[j] = k;
        }
        else {
            k = tempNext[k];
        }
    }

    int* tempNextVal = new int[length];
    tempNextVal[0] = -1;

    for (int i = 1; i < length; i++) {
        if (data[i] != data[tempNext[i]]) {
            tempNextVal[i] = tempNext[i];
        }
        else {
            tempNextVal[i] = tempNextVal[tempNext[i]];
        }
    }

    for (int i = 0; i < length; i++) {
        nextVal[i] = tempNextVal[i] + 1;
    }

    delete[] tempNext;
    delete[] tempNextVal;
}

int simpleMatch(const myStr& S, const myStr& T) {
    int i = 0, j = 0;
    while (i < S.length && j < T.length) {
        if (S.data[i] == T.data[j]) {
            i++;
            j++;
        }
        else {
            i = i - j + 1;
            j = 0;
        }
    }

    if (j == T.length) {
        return i - j + 1;
    }
    else {
        return -1;
    }
}

int kmpMatch(const myStr& S, const myStr& T) {
    if (T.length == 0) {
        return 1;
    }

    myStr T_temp(T.data);
    T_temp.kmp_nextVal();

    int i = 0, j = 0;
    while (i < S.length && j < T.length) {
        if (j == -1 || S.data[i] == T.data[j]) {
            i++;
            j++;
        }
        else {
            j = T_temp.nextVal[j] - 1;
        }
    }

    if (j == T.length) {
        return i - j + 1;
    }
    else {
        return -1;
    }
}

void myStr::print(){
    for(int i = 0; i < this->length; i++)
        cout << this->data[i];

    cout << endl;
}

void myStr::printNext(){
    for(int i = 0; i < length; i++)
        cout << next[i];
    cout << endl;
}

void myStr::printNextVal(){
    for(int i = 0; i < length; i++)
        cout << nextVal[i];
    cout << endl;
}

bool replaceStr(myStr& S, const int& start, const myStr& T, const myStr& V) {
    int pos = start - 1;

    if (pos < 0 || pos >= S.length) {
        return false;
    }

    int matchPos = -1;
    int i = pos, j = 0;

    while (i < S.length && j < T.length) {
        if (S.data[i] == T.data[j]) {
            i++;
            j++;
        }
        else {
            i = i - j + 1;
            j = 0;
        }
    }

    if (j == T.length) {
        matchPos = i - j;
    }
    else {
        return false;
    }

    int newLength = S.length - T.length + V.length;
    char* newData = new char[newLength + 1];

    for (int k = 0; k < matchPos; k++) {
        newData[k] = S.data[k];
    }

    for (int k = 0; k < V.length; k++) {
        newData[matchPos + k] = V.data[k];
    }

    for (int k = matchPos + T.length; k < S.length; k++) {
        newData[matchPos + V.length + (k - matchPos - T.length)] = S.data[k];
    }

    newData[newLength] = '\0';

    delete[] S.data;
    S.data = newData;
    S.length = newLength;

    delete[] S.next;
    delete[] S.nextVal;
    S.next = new int[S.length];
    S.nextVal = new int[S.length];

    return true;
}

myMatrix::myMatrix() {
    rowNum = 0;
    colNum = 0;
    nodeNum = 0;
    nodeList = NULL;
}

myMatrix::myMatrix(const int& rNum, const int& cNum, const int& nNum, const int* arr) {
    rowNum = rNum;
    colNum = cNum;
    nodeNum = nNum;

    if (nodeNum > 0) {
        nodeList = new matrixNode[nodeNum];

        for (int i = 0; i < nodeNum; i++) {
            nodeList[i].row = arr[i * 3];
            nodeList[i].col = arr[i * 3 + 1];
            nodeList[i].value = arr[i * 3 + 2];
        }

        sort(nodeList, nodeList + nodeNum, [](const matrixNode& a, const matrixNode& b) {
            if (a.row == b.row) {
                return a.col < b.col;
            }

            return a.row < b.row;
        });
    }
    else {
        nodeList = NULL;
    }
}

myMatrix::~myMatrix() {
    if (nodeList != NULL) {
        delete[] nodeList;
    }
}

void myMatrix::printMatrix(){
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for(int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}

void myMatrix::FastTransposeSMatrix(myMatrix& T) {
    T.rowNum = colNum;
    T.colNum = rowNum;
    T.nodeNum = nodeNum;

    if (nodeNum == 0) {
        T.nodeList = NULL;
        return;
    }

    T.nodeList = new matrixNode[nodeNum];

    int* colCount = new int[colNum + 1]();
    for (int i = 0; i < nodeNum; i++) {
        colCount[nodeList[i].col]++;
    }

    int* colStart = new int[colNum + 1]();
    colStart[1] = 0;
    for (int i = 2; i <= colNum; i++) {
        colStart[i] = colStart[i - 1] + colCount[i - 1];
    }

    for (int i = 0; i < nodeNum; i++) {
        int col = nodeList[i].col;
        int pos = colStart[col];

        T.nodeList[pos].row = nodeList[i].col;
        T.nodeList[pos].col = nodeList[i].row;
        T.nodeList[pos].value = nodeList[i].value;

        colStart[col]++;
    }

    delete[] colCount;
    delete[] colStart;
}